{ "cells": [ { "cell_type": "code", "execution_count": 1, "id": "54eac803-8049-46b2-ab08-c5a8c32657b4", "metadata": {}, "outputs": [], "source": [ "import copy\n", "\n", "class Tube:\n", " def __init__(self, volumn, balls):\n", " self.balls = balls\n", " self.volumn = volumn\n", " \n", " def drop(self):\n", " return self.balls.pop() if self.balls != 0 else False\n", " \n", " def add(self, ball):\n", " self.balls.append(ball)\n", " return\n", " \n", " def last_ball(self):\n", " return self.balls[-1] if len(self.balls) != 0 else None\n", " \n", " def consecute_color(self):\n", " if len(self.balls) == 0:\n", " return 0\n", " result = 0\n", " for _ in self.balls[::-1]:\n", " if _ == self.last_ball():\n", " result += 1\n", " else:\n", " return result\n", " return result\n", " \n", " def free_space(self):\n", " return self.volumn - len(self.balls)\n", " \n", "class Game:\n", " def __init__(self, tube_size, tubes_data):\n", " tubes = [ Tube(tube_size,_) for _ in tubes_data]\n", " self.tubes = tubes\n", " self.max_score = sorted([len(_.balls) for _ in tubes])\n", " self.solution = []\n", " color_stat = {}\n", " for tube in tubes:\n", " for ball in tube.balls:\n", " if ball in color_stat:\n", " color_stat[ball] += 1\n", " else:\n", " color_stat[ball] = 1\n", " print(color_stat.values())\n", " \n", " def move(self, id_from, id_to, num_ball):\n", " for _ in range(num_ball):\n", " self.tubes[id_to].add(self.tubes[id_from].drop())\n", " \n", " def get_stat(self):\n", " return {\n", " \"top_balls\": [_.last_ball() for _ in self.tubes],\n", " \"consecute_colors\": [_.consecute_color() for _ in self.tubes],\n", " \"free_spaces\": [_.free_space() for _ in self.tubes]\n", " }\n", " \n", " def __repr__(self):\n", " return str([_.balls for _ in self.tubes])\n", " \n", " def get_tubes(self):\n", " return [_.balls for _ in self.tubes]\n", " \n", " \n", "def reduce_list(input_list):\n", " a = input_list.copy()\n", " dropped_num = 0\n", " for i in range(1,len(a)):\n", " idx = i+dropped_num\n", " if a[idx][0] == a[idx-1][1] and a[idx][1] == a[idx-1][0]:\n", " a.pop(idx-1)\n", " dropped_num -= 1\n", " elif a[idx][0] == a[idx-1][1]:\n", " a[idx-1] = (a[idx-1][0],a[idx][1])\n", " return a\n", "\n", "def iterate(game, max_score, solution, history_move = [], history_tubes = [], direction = 1):\n", " tube_indexes = list(range(len(game.tubes)))\n", " #random.shuffle(tube_indexes)\n", " for i in tube_indexes[::direction]:\n", " if ( game.tubes[i].last_ball() == None):\n", " continue\n", " selected_ball = game.tubes[i].last_ball()\n", " num_selected_ball = game.tubes[i].consecute_color()\n", " #print(selected_ball,num_selected_ball)\n", " for j in tube_indexes[::-direction]:\n", " \n", " if ( i == j or \n", " game.tubes[j].free_space() < num_selected_ball or \n", " game.tubes[j].last_ball() not in [None, selected_ball] ): \n", " continue\n", " if ( game.tubes[j].consecute_color() == 0 and\n", " game.tubes[i].consecute_color() == len(game.tubes[i].balls)):\n", " continue\n", " from_id = i\n", " to_id = j\n", " temp_game = copy.deepcopy(game)\n", " tube_i_remain = len(temp_game.tubes[i].balls) - num_selected_ball\n", " if ( temp_game.tubes[i].balls[:tube_i_remain] == temp_game.tubes[j].balls[:tube_i_remain] and\n", " temp_game.tubes[j].consecute_color() <= temp_game.tubes[i].free_space() and\n", " temp_game.tubes[i].consecute_color() > temp_game.tubes[j].consecute_color() > 0 ):\n", " \n", " from_id = j\n", " to_id = i\n", " num_selected_ball = temp_game.tubes[j].consecute_color()\n", " temp_game.move(from_id,to_id,num_selected_ball)\n", " \n", " current_score = sorted(temp_game.get_stat()[\"consecute_colors\"]) \n", " current_tubes = temp_game.get_tubes()\n", " \n", " if current_tubes in history_tubes:\n", " return False\n", " if current_score == max_score: \n", " return history_move+[(from_id+1,to_id+1)]\n", " else:\n", " result = iterate(temp_game,max_score,solution,history_move+[(from_id+1,to_id+1)],history_tubes+[current_tubes])\n", " if result:\n", " if isinstance(result, list):\n", " solution.append(reduce_list(result))\n", " if len(solution) > sum(max_score)**2:\n", " return True\n", "\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "93d28018-d3c0-472e-ab8c-82d476000f16", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "dict_values([4, 4, 4])\n" ] } ], "source": [ "## Init Tubes\n", "game = Game(4,[[5,3,1,5],[3,1,3,3],[1,5,5,1],[]])\n", " " ] }, { "cell_type": "raw", "id": "eacd91c7-2299-4cd9-846c-4f09c0f57a57", "metadata": {}, "source": [ "color_code_map = {\n", " \"white\": 0,\n", " \"red\": 1,\n", " \"orange\": 2,\n", " \"yellow\": 3,\n", " \"green\": 4,\n", " \"blue\": 5,\n", " \"indigo\": 6,\n", " \"violet\": 7,\n", " \"pink\": 8,\n", " \"pale\":9\n", "}" ] }, { "cell_type": "code", "execution_count": 3, "id": "d061225e-4b91-4ebd-9520-0c97ff053962", "metadata": {}, "outputs": [], "source": [ "iterate(game,game.max_score,game.solution)" ] }, { "cell_type": "code", "execution_count": 4, "id": "1eb356a6-4036-4e8d-b1f2-e709e23e3e09", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "8\n" ] }, { "data": { "text/plain": [ "[(1, 4), (3, 1), (3, 4), (1, 3), (2, 1), (2, 3), (1, 2), (1, 4)]" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "best_sol = sorted([reduce_list(_) for _ in game.solution] ,key=lambda x : len(x))[0]\n", "print(len(best_sol))\n", "best_sol" ] }, { "cell_type": "code", "execution_count": null, "id": "0ed491bb-d37d-411f-96ed-ff6e2e486e7f", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.8.10" } }, "nbformat": 4, "nbformat_minor": 5 }